#include<stdio.h>
#include<malloc.h>

struct node{
	int num;
	struct node *prev;
	struct node *next;
};

struct node *head;

int insert(int);

int delnode(int);

int printlist();

int main(){
	int choice, num;
	printf("----Doubly Linked List----");
	printf("\nWhat do you want to do?");
	printf("\n1. View list\n2. Insert Number\n3. Delete number\n4. Exit\t");

	scanf("%d", &choice);
	do{
		if(head==NULL)
			printf("\n--List is Empty right now");
		switch(choice){
			case 1: printlist(); break;
			case 2: printf("\nEnter number to insert:");
				scanf("%d", &num);
				insert(num);
				break;
			case 3: printf("\nEnter number to delete:");
				scanf("%d", &num);
				delnode(num);
				break;
			case 4: printf("\n--Exiting Program");
				exit(0);
			default: printf("\n--Pushing back to menu--");
		}
		printf("\n--Menu--\n1. View list\n2. Insert number\n3. Delete number\n4.Exit\t");
		scanf("%d", &choice);
	}while(choice!=4);
	return 0;
}

int insert(int n){
	if(head == NULL){
		/* If this is the first element */
		struct node *p;
		p = (struct node*)malloc(sizeof(struct node));
		p->num = n;
		p->prev = NULL;
		p->next = NULL;
		head = p;
	}else{
		struct node *p, *q;
		p = head;
		while(p->next != NULL){
			p = p->next;
		}
		q = (struct node *)malloc(sizeof(struct node));
		q->num = n;
		q->next = NULL;
		p->next = q;
		q->prev = p;
	}
}

int delnode(int n){
	if(head == NULL){
		printf("\nLinked List is Empty");
	}else{
		struct node *p = head, *prev = NULL, *next;
		while(p->num != n && p->next != NULL){
			prev = p;
			p = p->next;
		}
		if(p->num != n && p->next == NULL){
			printf("\nThe value %d not found in the list", p->num);
		}else if(p == head && p->num){
			printf("\nValue %d found and deleted from the head", p->num);
			head->next->prev = NULL;
			p = head;
			head = head->next;
			free(p);
		}else{
			next = p->next;
			prev->next = next;
			next->prev = prev;
			free(p);
		}
	}
}

int printlist(){
	if(head == NULL){
		printf("\nLinked List is empty");
	}else{
		struct node *p = head;
		do{
			printf("\nValue: %d", p->num);
			p = p->next;
		}while(p);
	}
}
